package gold.digger;

import gold.vo.TreeNode;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC652 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        public Map<String, Integer> dict = new LinkedHashMap<>();
        public Map<TreeNode, String> preMap = new HashMap<>();
        public Map<TreeNode, String> midMap = new HashMap<>();

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            List<TreeNode> res = new ArrayList<>();
            findDuplicateSubtreesRecur(root, res);
            return res;
        }


        public void findDuplicateSubtreesRecur(TreeNode root, List<TreeNode> res) {
            if (null == root) return;
            findDuplicateSubtreesRecur(root.left, res);
            findDuplicateSubtreesRecur(root.right, res);
            String mid = "";
            String pre = "";

            mid = (null != root.left && midMap.get(root.left) != null) ? midMap.get(root.left) : ",null";
            mid = mid + "," + root.val;
            mid += (null != root.right && midMap.get(root.right) != null) ? midMap.get(root.right) : ",null";

            pre = "," + root.val;
            pre += (null != root.left && preMap.get(root.left) != null) ? preMap.get(root.left) : ",null";
            pre += (null != root.right && preMap.get(root.right) != null) ? preMap.get(root.right) : ",null";

            preMap.put(root, pre);
            midMap.put(root, mid);

            String totalMap = pre + mid;
            if (dict.containsKey(totalMap)) {
                int count = dict.get(totalMap).intValue();
                if (count == 1) res.add(root);
                dict.put(totalMap, dict.get(totalMap) + 1);
                return;
            }

            dict.put(totalMap, 1);
        }
    }

    public void run() {
        Solution solution = new Solution();
        TreeNode ro = TreeNode.createTree("[0,0,0,0,null,null,0,null,null,null,0]");
//        TreeNode ro = TreeNode.createTree("1,2,2");
        System.out.println(solution.findDuplicateSubtrees(ro));
    }

    public static void main(String[] args) throws Exception {
        LC652 an = new LC652();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
